#include "stdafx.h"
#include "tango frenzy.h"

extern int numar_noduri;
extern nod* headref;
extern nod * headtango;
extern lista *first;

lista* vechifirst;
nod* vechiheadref;
nod *vechiheadtango;

extern int v[32];
extern int nr;
extern int q;

int a[40][40];

void interpret_matr(nod *root)
{
	if (root==NULL)
		return;
	if (a[root->info][0]==13) root->isroot=1;
	if (root->left)
			if (a[root->info][root->left->info]==1) root->preferatstg=1;
	if (root->right)
		if (a[root->info][root->right->info]==1) root->preferatdreapta=1;
	interpret_matr(root->left);
	interpret_matr(root->right);
}

void parc_ttree(nod * root)
{
	if (root==NULL) return;
	if (root->left)
	{
		a[root->info][root->left->info]=1;
		a[root->left->info][root->info]=1;
	}
	if (root->right)
	{
		a[root->info][root->right->info]=1;
		a[root->right->info][root->info]=1;
	}
	parc_ttree(root->left);
	parc_ttree(root->right);
}

void parc_lista(lista* el)
{
	if (el==NULL) return;
	a[el->radacina->info][0]=13;
	parc_ttree(el->radacina);
	parc_lista(el->next);
}

void initializari()
{
	int i,j;
	for (i=0;i<35;i++)
		for (j=0;j<35;j++)
			a[i][j]=0;
	q=0;
	headref=creare_reftree(0,numar_noduri+1,0);
	parc_lista(vechifirst);
	interpret_matr(headref);
}


void recreate_ref()
{
	initializari();
}

void umplere_vect(nod * root)
{
	if (root==NULL) return;
	v[nr]=root->info;
	nr++;
	umplere_vect(root->left);
	umplere_vect(root->right);
}


void echilibrare()
{
	nod* root=first->radacina,*nn=NULL;
	lista *el,*o,*p;
	nr=1;
	umplere_vect(root);
	nn=crearearbore();
	nn->isroot=1;
	freememnod(root);
	first->radacina=nn;
	el=first;
	first=first->next;
	el->next=NULL;
	o=first;
	p=o;
	while (o!=NULL)
		if (o->nrelem>=el->nrelem)
		{
			p=o;
			o=o->next;
		}
		else o=NULL;
	el->next=p->next;
	p->next=el;
}



int detnrelem(nod *root)
{
	int i=1;
	if (root==NULL) return 0;
	i=i+detnrelem(root->left)+detnrelem(root->right);
	return i;
}
	


void parcurgeretango(int info)
{
	nod *nxt=NULL,*crt=headtango,*r=NULL,*t=NULL;
	lista *lis=NULL,*ult=NULL,*lst=NULL,*el=NULL,*o,*p;
	while (crt->info!=info)
	{
		if (crt->info>info) 
			{
				nxt=crt->left;
				r=crt->right;
		}
		else {
			nxt=crt->right;
			r=crt->left;
		}
	
		if (nxt->isroot==1)
		{
			lis=first;
			while (lis->radacina->info!=nxt->info) 
				{
					ult=lis;
					lis=lis->next;
			}
			if (first==lis)
					first=first->next;
			else 
				ult->next=lis->next;
			lis->radacina->isroot=0;
		
			if (r!=NULL)
			{
			if (r->isroot!=1)
			{
				t=first->radacina;
				while (t->info!=crt->info)
					if (t->info<crt->info) t=t->right;
					else t=t->left;
				if (t->info<info) 
					{
						t->right=lis->radacina;
						
						if (t->left)
						{

						t->left->isroot=1;		
						el=NULL;
						el=(lista *)malloc(sizeof(lista));
						el->nrelem=detnrelem(t->left);
						el->radacina=t->left;
						t->left=NULL;
						first->nrelem=detnrelem(first->radacina);
						
						o=first;
						p=o;
						while (o!=NULL)
							if (o->nrelem>el->nrelem)
							{
								p=o;
								o=o->next;
							}
							else o=NULL;
						el->next=p->next;
						p->next=el;
						}
				}


				else 
					{
						t->left=lis->radacina;
						if (t->right)
						{
						t->right->isroot=1;
						el=NULL;
						el=(lista*)malloc(sizeof(lista));
						el->nrelem=detnrelem(t->right);
						el->radacina=t->right;
						t->right=NULL;
						first->nrelem=detnrelem(first->radacina);

						o=first;
						p=o;
						while (o!=NULL)
							if (o->nrelem>el->nrelem)
							{
								p=o;
								o=o->next;
							}
							else o=NULL;
						el->next=p->next;
						p->next=el;
						}
				}
				}
			else
			{ //daca r e root si nxt e root??
				t=first->radacina;
				while (t->info!=crt->info)
					if (t->info<crt->info) t=t->right;
					else t=t->left;
				lis->radacina->isroot=0;
				if (t->info<info) 
						t->right=lis->radacina; 
				else 
					t->left=lis->radacina;
				first->nrelem=detnrelem(first->radacina);
			}

			}
			
			else
			{
				//daca r e null si nxt e root
				t=first->radacina;
				while (t->info!=crt->info)
					if (t->info<crt->info) t=t->right;
					else t=t->left;
				lis->radacina->isroot=0;
				if (t->info<info) 
						t->right=lis->radacina; 
				else 
					t->left=lis->radacina;
				first->nrelem=detnrelem(first->radacina);
			}
		}
		else if (r!=NULL)
		{
			if (r->isroot!=1)
		{
			t=first->radacina;
			while (t->info!=crt->info)
				if (t->info<crt->info) t=t->right;
				else t=t->left;
			if (t->info<info) 
				{
					if (t->left)
					{
					t->left->isroot=1;	
					el=NULL;
					el=(lista *)malloc(sizeof(lista));
					el->nrelem=detnrelem(t->left);
					el->next=NULL;
					el->radacina=t->left;
					t->left=NULL;
					first->nrelem=detnrelem(first->radacina);
						
					o=first;
					p=o;
					while (o!=NULL)
						if (o->nrelem>el->nrelem)
						{
							p=o;
							o=o->next;
						}
						else o=NULL;
					el->next=p->next;
					p->next=el;
					}
			}


			else 
				{
					if (t->right)
					{
					t->right->isroot=1;
					el=NULL;
					el=(lista*)malloc(sizeof(lista));
					el->nrelem=detnrelem(t->right);
					el->radacina=t->right;
					t->right=NULL;
					first->nrelem=detnrelem(first->radacina);

					o=first;
					p=o;
					while (o!=NULL)
						if (o->nrelem>el->nrelem)
						{
							p=o;
							o=o->next;
						}
						else o=NULL;
					el->next=p->next;
					p->next=el;
					}
			}
		}
			else
			{
				//nxt nu e root, r e root
			}
			}
		crt=nxt;
	}

}
	

void tangosearch(int info)		//creaza noile valori si le salveaza in variabilele vechi..
{
	nod *oops;
	lista *ooops,*rzv;
	
	nr=1;


	copiere();
	parcurgeretango(info);			// nu merge prea bine!
	//
	rzv=first;
	while(rzv!=NULL)
	{
		rzv->nrelem=detnrelem(rzv->radacina);
		rzv=rzv->next;
	}
	echilibrare();
	echilibrare();
	rzv=first;
	while (rzv->next)
	{
		aranjare_lista(rzv,rzv->next);	// pe 31 nu merge?!
		rzv=rzv->next;
	}
	ooops=first;
	first=vechifirst;
	vechifirst=ooops;
	headtango=NULL;
	createtango(vechifirst);				//vechifirst daca scot comentariile
	oops=headtango;
	headtango=vechiheadtango;
	vechiheadtango=oops;

	headref=NULL;
	recreate_ref();
	oops=headref;
	headref=vechiheadref;
	vechiheadref=oops;

}

void freelista(lista *el)
{
	if (el==NULL) return;
	freelista(el->next);
	freememnod(el->radacina);
	free(el);
	el=NULL;
	return;
}


void freetangotree()			//face free valorilor vechi si le actualizeaza cu cele din vechi...
{
	freelista(first);
	first=vechifirst;
	freememnod(headref);
	headref=vechiheadref;
	freememnod(headtango);
	headtango=vechiheadtango;
}